package com.duing.backTracking;

import java.util.ArrayList;
import java.util.List;

public class SubSet {

    public static void main(String[] args) {
        int[] nums = {5, 1, 6};
        List<List<Integer>> result = subsets2(nums);
        System.out.println(result.toString());
    }

     //暴力循环法
     //以当前元素结尾的所有子集
     //{5,1,6}
     //[]
     //[5]
     //[1]  [5,1]
     //[6]  [5,6]  [1,6]  [5,1,6]
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        result.add(new ArrayList<>());
        // size = 1  {{}}

        for (int num : nums) {
            // 以当前已有的子集个数为依据  处理第i+1个元素
            int size = result.size();
            // num=5  size=1
            // num=1  size=2
            // num=6  size=4
            for (int i = 0; i < size; i++) {
                // 先依次取出已有的子集  然后添加新的元素  构成新的子集
                List<Integer> sub = new ArrayList<>(result.get(i));
                sub.add(num);
                result.add(sub);
                // size=2  num=5   {{},{5}}
                // size=4  num=1   {{},{5},{1},{5,1}}
                // size=8  num=6   {{},{5},{1},{5,1},{6},{5,6},{1,6},{5,1,6}}
            }
        }
        return result;
    }

     // 0 1 2  j
     //{5,1,6}   n个元素 有2^n个子集
     //[]
     //[5]
     //[1]  [5,1]
     //[6]  [5,6]  [1,6]  [5,1,6]
     // 000  001  010  011  100  101  110  111  (1000)  0-7的二进制  设为i(当前处理的子集索引)
     // 将0看做不取值，1看做取值
     //
     // 根据子集的个数遍历 2^n 次   在每一次遍历时  要遍历数组本身  决定取或不取元素
     //
     //2^n如何写？  1<<n 左移
     // n    0    1    2
     //2^n   1    2    4
     //1<<n  001  010  100
     //
     //0 1 2    遍历数组本身的索引 设为j
     //1 2 4    001  010  100    2^j = (1<<j)
     //
     //&运算   0&0=0&1=1&0=0  1&1=1
     //00 & 01 = 00   01 & 11 = 01
     //
     //非运算  ~0
     //
     //i   000  001  010  011  100  101  110  111
     //
     //i      2^j                 result（i & 2^j ）            {5,1,6}
     //000    001  010  100       000  000  000    [0,0,0]     {}
     //001    001  010  100       001  000  000    [~,0,0]     {5}
     //
     //100    001  010  100       000  000  100    [0,0,~]     {6}
     //101    001  010  100       001  000  100    [~,0,~]     {5,6}
     //
     //111    001  010  100       001  010  100    [~,~,~]     {5,1,6}

    public static List<List<Integer>> subsets1(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        int n = nums.length;
        // 2^n如何写？  1<<n 左移
        for (int i = 0; i < (1 << n); i++) {
            List<Integer> tmp = new ArrayList<>();
            for (int j = 0; j < n; j++) {
                if ((i & (1 << j)) != 0) {
                    tmp.add(nums[j]);
                }
            }
            result.add(tmp);
        }
        return result;
    }


     //回溯
     //{5,1,6}
     //以当前元素开头的所有子集
     //{5,1,6}  {5,1}  {5,6}  {5}
     //{1,6}  {1}
     //{6}
     //
     //路径  选择列表  结束条件
     // result = []
     // function(路径，选择列表)
     //    if 满足结束条件   result.add(路径)  return
     //    for 选择 in 选择列表
     //       做选择
     //       function(路径下一步，选择列表)
     //       撤销选择

    static List<List<Integer>> result = new ArrayList<>();
    static List<Integer> tmp = new ArrayList<>();

    public static List<List<Integer>> subsets2(int[] nums) {
        dfs(0, nums);
        return result;
    }

    // {} {5} {5,1} {5,1,6}
    // {5,1}   ->  {5}
    // {5,6}   ->  {5}
    // {5}     ->  {}
    // {1} {1,6}
    // {1}     ->  {}
    // {6}     ->  {}
    public static void dfs(int cur, int[] nums) {
        if (cur == nums.length) {
            // cur=3  tmp={5,1,6}
            //        tmp={5,1}
            //        tmp={5,6}
            //        tmp={5}
            result.add(new ArrayList<>(tmp));
            return;
        }
        // cur=0  nums[0]=5  tmp={5}
        // cur=1  nums[1]=1  tmp={5,1}
        // cur=2  nums[2]=6  tmp={5,1,6}
        tmp.add(nums[cur]);
        dfs(cur + 1, nums);
        //tmp.remove(nums[cur]);
        tmp.remove(tmp.size() - 1);
        // cur=2  tmp={5,1}
        // cur=1  tmp={5}
        // cur=2  tmp={5,6}
        dfs(cur + 1, nums);
    }
}
